package com.algrithom.graph.mincreatetree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import com.common.model.Edge;
import com.common.model.WeightGraph;

import lombok.Getter;

/**
 * 最小生成树 存储结构为：边集数组
 *
 * @author think
 * @since 2020/3/8
 */
public class KrushkalAlg {
    
    @Getter
    private final List<Edge> mst = new ArrayList<>();
    
    /**
     * 求最小树的Kruskal算法 算法思想：克鲁斯卡尔算法从另一个途径求网中的最小生成树。假设联通网N=(nodes,{edges})，则令
     * 最小生成树的厨师状态为只有n个顶点而无边的非连通图T=(nodes,{})，途中每个顶点自称一个连通分量。
     * 在E中选择代价最小的边，若该边衣服的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边 而选择下一条最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。
     */
    public void kruskal(WeightGraph graph){
        // 构造Edge的最小堆
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));
        
        // 1. 将所有的边添加到最小堆中
        minHeap.addAll(graph.getEdges());
        
        // 2. 创建并查集，保存顶点间的连通关系
        UnionFind unionFind = new UnionFind(graph.getNodeNum());
        
        // 3. 收集到mst的边数 = 顶点数 - 1时即完成最小生成树的边数收集
        while (!minHeap.isEmpty() && mst.size() < graph.getNodeNum() - 1) {
            Edge minEdge = minHeap.poll();
            // 判断顶点是否连通成环，不成环则加入mst
            if (unionFind.find(minEdge.getSrcNode(),minEdge.getDstNode())) {
                continue;
            }
            // 加入mst和并查集
            mst.add(minEdge);
            unionFind.union(minEdge.getSrcNode(),minEdge.getDstNode());
        }
    }
    
    public int getMstWeight(){
        // 将mst中的权值累加返回
        return mst.stream().mapToInt(Edge::getWeight).sum();
    }
}
